<?php
/**
 * <https://y.st./>
 * Copyright © 2019 Alex Yst <mailto:copyright@y.st>
 * 
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program. If not, see <https://www.gnu.org./licenses/>.
**/

$xhtml = array(
	'<{title}>' => 'Sharing forks',
	'takedown' => '2017-11-01',
	'<{body}>' => <<<END
<img src="/img/CC_BY-SA_4.0/y.st./weblog/2019/04/26.jpg" alt="Pink flowers amongst tree branches" class="framed-centred-image" width="800" height="480"/>
<section id="diet">
	<h2>Dietary intake</h2>
	<p>
		I ate a peanut butter and jelly sandwich when I got up.
		For lunch, I didn&apos;t have time to come up with much, so I just had 198 grams of salsa and 54 grams of corn chips.
		For dinner, I brought a veggie patty and dairy-free cheese sandwich with a pickle, ketchup, and mustard to work.
	</p>
</section>
<section id="drudgery">
	<h2>Drudgery</h2>
	<p>
		My discussion post for the day:
	</p>
	<blockquote>
		<p>
			I think the discussion post needs to be updated for future iterations of the course.
			It seems to be based on an older version of the textbook, or something.
			Figure 30.11 has to do with put and get routines, not the dining philosophers.
			The dining philosophers are dealt with in Figures 31.14 - 31.16.
		</p>
		<p>
			The book makes the claim that no philosopher will be waiting for another to put down the second fork they need after we change the order in which philosopher #4 acquires forks <a href="http://pages.cs.wisc.edu/~remzi/OSTEP/threads-sema.pdf">(Arpaci-Dusseau &amp; Arpaci-Dusseau, 2012)</a>.
			This is untrue.
			What&apos;s actually the case is that philosopher #4 and philosopher #0 won&apos;t hold one fork while waiting for the fork they share, and deadlocks can only occur between all philosophers at once.
			Thus, there can be no deadlocks.
			Philosophers can still get stuck waiting for forks, they just won&apos;t have to wait indefinitely.
		</p>
		<p>
			So why is philosopher #4, with their reversed fork-acquisition order, so special?
			Well, it has to do with the impact a philosopher&apos;s fork-acquisition order has on the adjacent forks.
			First, let&apos;s look at the broken solution.
			Each fork #n can be acquired as philosopher #n&apos;s first fork or philosopher #(n+4)%5&apos;s second fork.
			(Because each philosopher #n acquires fork #(n+1)%5 as their second fork <a href="http://pages.cs.wisc.edu/~remzi/OSTEP/threads-sema.pdf">(Arpaci-Dusseau &amp; Arpaci-Dusseau, 2012)</a>, each fork #n is acquired as a second fork by philosopher #(n+4)%5.)
			Let&apos;s build a table to visualise:
		</p>
		<table>
			<thead>
				<tr>
					<th>
						Fork #n
					</th>
					<th>
						0
					</th>
					<th>
						1
					</th>
					<th>
						2
					</th>
					<th>
						3
					</th>
					<th>
						4
					</th>
				</tr>
			</thead>
			<tbody>
				<tr>
					<th>
						philosopher #n
					</th>
					<td>
						first
					</td>
					<td>
						first
					</td>
					<td>
						first
					</td>
					<td>
						first
					</td>
					<td>
						first
					</td>
				</tr>
				<tr>
					<th>
						Philosopher #(n+4)%5
					</th>
					<td>
						second
					</td>
					<td>
						second
					</td>
					<td>
						second
					</td>
					<td>
						second
					</td>
					<td>
						second
					</td>
				</tr>
			</tbody>
		</table>
		<p>
			That table doesn&apos;t look like it tells us anything interesting, but it will when we compare it to a second table in a bit.
			Now let&apos;s reverse philosopher #4&apos;s fork-acquisition order.
			That is, let&apos;s implement the working solution proposed by the textbook <a href="http://pages.cs.wisc.edu/~remzi/OSTEP/threads-sema.pdf">(Arpaci-Dusseau &amp; Arpaci-Dusseau, 2012)</a>.
			Now, philosopher #4 grabs fork #0 as their first fork.
			To state that in reverse, fork #0 is grabbed by philosopher #4 (philosopher #(n+4)%5, from fork #0&apos;s perspective) as their first fork.
			Likewise, fork #4 will be grabbed by philosopher #4 (philosopher #n, from fork #4&apos;s perspective) as their second fork.
			Let&apos;s see how that mixes up the table a bit:
		</p>
		<table>
			<thead>
				<tr>
					<th>
						Fork #n
					</th>
					<th>
						0
					</th>
					<th>
						1
					</th>
					<th>
						2
					</th>
					<th>
						3
					</th>
					<th>
						4
					</th>
				</tr>
			</thead>
			<tbody>
				<tr>
					<th>
						philosopher #n
					</th>
					<td>
						first
					</td>
					<td>
						first
					</td>
					<td>
						first
					</td>
					<td>
						first
					</td>
					<td>
						second
					</td>
				</tr>
				<tr>
					<th>
						Philosopher #(n+4)%5
					</th>
					<td>
						first
					</td>
					<td>
						second
					</td>
					<td>
						second
					</td>
					<td>
						second
					</td>
					<td>
						second
					</td>
				</tr>
			</tbody>
		</table>
		<p>
			In this arrangement, fork #0 is <strong>*always*</strong> chosen as the first fork by any philosopher that would use it.
			That means that if a philosopher is going to use fork #0, they absolutely will not hold onto another fork while they wait.
			That leaves their other fork available to be grabbed by another philosopher.
			As such, philosopher #0 and philosopher #4, which share fork #0, will not tie up forks in such a way to cause a deadlock.
			And as mentioned before, a deadlock can only occur between all philosophers at once.
			Otherwise, there&apos;s just sort of a domino effect where philosophers have to wait their turn, but don&apos;t end up starving.
		</p>
		<p>
			As a side note, on the other end of things, we can look at fork #4&apos;s special properties as well.
			Fork #4 will always be a second fork.
			That means that when one philosopher is waiting for that fork, they know the philosopher currently holding it already has two forks.
			Because they have two forks, they aren&apos;t waiting for a second fork, so any philosopher waiting for fork #4 knows that they won&apos;t have to wait forever.
			Again, this breaks the possibility of a deadlock.
		</p>
		<div class="APA_references">
			<h3>References:</h3>
			<p>
				Arpaci-Dusseau, A., &amp; Arpaci-Dusseau, R. (2012). <a href="http://pages.cs.wisc.edu/~remzi/OSTEP/threads-sema.pdf">31: Semaphores</a>. Retrieved from <code>http://pages.cs.wisc.edu/~remzi/OSTEP/threads-sema.pdf</code>
			</p>
		</div>
	</blockquote>
</section>
<section id="prayer">
	<h2>Prayer impressions log</h2>
	<p>
		I prayed that I&apos;d be reading the seventh chapter of Genesis, and that it would likely be the continuation of the Noah&apos;s ark arc.
		I said it would be interesting to see what didn&apos;t make sense in that chapter.
		In my mind, I saw a cartoon squirrel, spinning rapidly on two legs with its tail wrapped around it, then falling over.
	</p>
	<p>
		Afterwards, I prayed that while the Noah&apos;s ark arc hadn&apos;t reached its conclusion just yet, this continuation certainly did have plenty of things that didn&apos;t add up in it.
		After I prayed, I saw a cartoon fox wandering about on two legs in my mind.
	</p>
</section>
<section id="poetic">
	<h2>Poetic thoughts</h2>
	<p>
		One of my workmates shared some poetic thoughts today.
		First, they said that anxiety is just spicy thoughts.
		I&apos;m not sure I quite agree, but I see what they mean.
		And second, they said that ice skating is just cursive walking.
		That was a really elegant analogy.
	</p>
</section>
END
);
